class Trie {
  bool isEnd; //该结点是否是一个串的结束
  Trie* next[26]; //字母映射表
public:
  /** Initialize your data structure here. */
  Trie() {

    this->isEnd = false;
    memset(this->next, 0, sizeof(next));
  }

  /** Inserts a word into the trie. */
  void insert(string word) {

    Trie *node = this;
    for(char c : word){
      if(node->next[c - 'a'] == nullptr){
        node->next[c - 'a'] = new Trie();
      }
      node = node->next[c - 'a'];
    }
    node->isEnd = true;
  }

  /** Returns if the word is in the trie. */
  bool search(string word) {

    Trie *node = this;
    bool f = true;
    for(char c : word){
      if(node->next[c - 'a']){
        node = node->next[c - 'a'];
        continue;
      }
      f = false;
      break;
    }

    return f && node->isEnd;

  }

  /** Returns if there is any word in the trie that starts with the given prefix. */
  bool startsWith(string prefix) {

    Trie *node = this;
    bool f = true;
    for(char c : prefix){
      if(node->next[c - 'a']){
        node = node->next[c - 'a'];
        continue;
      }
      f = false;
      break;
    }

    return f;

  }
};
